Online-Academy
Look, Read, Understand, Apply

Data Structure

Graph Q and A

What is a graph? How graph can be represented in computer?

Answer: Graph is a hierarchical data structure consisting of nodes (vertices) and edges (arcs). Graph can be used to represent computer network, cities, geographical maps of several locations, electrical circuits and many more. In computer two-dimensional array, linked list, adjacency matrix can be used to represent graph.

How graphs can be traversed?

Answer: Graph traversal means visiting each node (vertex) of graph once. Depth first traversal (DFT) or Breadth First Traversal (BFT) can be used to traverse a graph.

What is minimum spanning tree (MST)? What algorithms are used to find a minimum spanning tree of a graph?

Answer: Minimum spanning tree is a tree consisting of all the nodes of a graph with minimum weight. Dijkastras, Prims algorithms can be used to find minimum spanning tree from a graph.

What is a topological Sort?

Answer: Topological sort is a linear ordering of the vertices in a directed acyclic graph (DAG) such that for every directed edge u--> v, vertex u comes before vertex v in the ordering. Topological sort if possible for only directed acyclic graphs with no cycles.

Write the applications of topological sort.

Answer: For scheduling tasks, course prerequisites, build systems where some files must be processes before others.

For what purpose Floyd-Warshall algorithm used? What is time complexity of this algorithm? What are the applications of this algorithm?

The Floyd-Warshall algorithm is used to find the shortest paths between all pairs of vertices in a weighted graph (directed or undirected). Time complexity: O(V3) where V is the number of vertices. Finding shortest travel time between all pairs of cities. Network routing (e.g., computing routing tables). Game AI (pathfinding in game maps with pre-computation).

Which data structure is used to implement BFS and DFS algorithms?

Answer: Stack is used for DFS and Queue is used for BFS.

Write algorithm for Breadth First Search.

Answer:

  • Initialize an empty queue Q
  • Mark all vertices as unvisited
  • Mark the start node s as visited and enqueue it into Q
  • While Q is not empty:
    • Dequeue a vertex v from Q
    • Process v (e.g., print or store it)
    • For each neighbor u of v:

      • If u is unvisited:

      Mark u as visited

      Enqueue u into Q

Write algorithm for depth first search.

Answer:

  1. Mark all vertices as unvisited
  2. Define a recursive function DFS(v):
    1. Mark v as visited
    2. Process v (e.g., print or store it)
    3. For each neighbor u of v:
    4. If u is unvisited:
    5. Call DFS(u)
  4. Call DFS(s)

Write Dijkstras shortest path algorithm.

Answer:

  • Set distance to the source node as 0 and all other nodes as infinity.
  • Mark all nodes as unvisited.
  • Add the source node to the priority queue.
  • Extract the node (u) with the smallest distance from the priority queue.
  • For each neighbor (v) of u:
  • Calculate new_distance = distance[u] + weight(u, v).
  • If new_distance < distance[v], update distance[v] and add (v, new_distance) to the queue.
  • Mark u as visited (optional optimization to skip processed nodes).
  • The algorithm ends when the priority queue is empty.
  • The distance array now contains the shortest paths from the source.

Write Kruskals shortest path algorithm.

Answer: Kruskals MST algorithm is edge-based and its time complexity is O(E log(E)).

  • Sort all edges in non-decreasing order of weight.
  • Initialize DSU (each node is its own parent).
  • For each edge (u, v, weight) in sorted order:
  • If u and v are not in the same set (no cycle), add the edge to MST.
  • Union(u, v) in DSU.
  • Stop when (V-1) edges are selected (since MST has V-1 edges for V nodes).

What are the time complexities for Dijkstras shortest path algorithm, and Kruskals algorithm for minimum spanning tree.

Answer: For Dijkstras shortest path: 

If a Min-Heap (Priority Queue) is used:	O(V+E) * log(V)
	(where V = number of vertices, E = number of edges)
If an Array (No Heap) is used:
O(V2) (slower, but useful for dense graphs)
For Kruskals Minimum Spanning Tree: O(E*log(E)) or O(E*log(V)).

Write Prims Minimum spanning tree algorithm.

Answer: Prims MST algorithm is based on vertex-based and its time complexity is O(E*log(V)).

  • Set key[start] = 0 and all other key[v] = infinity.
  • Set parent[start] = -1.
  • Add all vertices to the priority queue (or just start with key=0).
  • While the priority queue is not empty:
  • Extract vertex u with the smallest key.
  • Mark u as visited.
  • For each neighbor v of u:
  • If v is unvisited and weight(u,v) < key[v]:
  • Update key[v] = weight(u,v).
  • Set parent[v] = u.
  • Adjust the priority queue (if v is already in it).

Write Floyd-Warshall all-short-path algorithm.

Answer:

  • Initialize a distance matrix dist where:
  • dist[i][j] = 0 if i == j.
  • dist[i][j] = weight(i,j) if there is a direct edge i--> j.
  • dist[i][j] = infinity otherwise.
  • For each intermediate vertex k (from 1 to V):
  • Update dist[i][j] to be the minimum of:
  • Current dist[i][j], or
  • dist[i][k] + dist[k][j] (path through k).
  • After all iterations, dist[i][j] contains the shortest path from i to j.